package 面试经典150题.图;

/**
 * @author tmh
 * @date 2024/6/26 20:35
 * @descriptionhttps://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/?envType=study-plan-v2&envId=top-interview-150
 *
 */
public class T200岛屿数量 {
    //这个人写的这个文章写的真好，醍醐灌顶了
    //https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/?envType=study-plan-v2&envId=top-interview-150
    public int numIslands(char[][] grid) {
        //定义一个岛屿数量
        int count = 0;
        int m = grid.length;
        int n = grid[0].length;
        //两个for循环来遍历网格中的所有陆地
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //取出所有陆地
                if (grid[i][j] == '1') {
                    //遍历
                    dfs(grid, i, j);
                    //岛屿数量+1
                    count++;
                }
            }
        }
        return count;

    }

    public void dfs(char[][] grid, int i, int j) {
        //判断格子是否在网格里面,不在网格里面中止遍历
        if (!inArea(grid, i, j)) {
            return;
        }
        //如果这个格子不是陆地，直接返回
        if (grid[i][j] != '1') {
            return;
        }
        //把当前这个格子标记位已经访问过
        grid[i][j] = '2';
        //上下左右分别继续遍历格子
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);

    }

    //判断坐标(r,c)是否在网格中
    public boolean inArea(char[][] grid, int row, int column) {
        return 0 <= row && row < grid.length && column >= 0 && column <=grid[0].length;
    }
}
